package main.剑指OfferⅠ;

import java.util.Arrays;

public class Day29 {
    public static void main(String[] args) {//AC自动机
        System.out.println("剑指Offer19.正则表达式匹配");
        System.out.println("剑指Offer49.丑数");
        System.out.println("剑指Offer60.n个骰子的点数");
    }
}

class Offer19{
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

class Offer49{
    public int nthUglyNumber(int n) {
        int[] dp=new int[n+1];
        dp[1]=1;
        int p2=1,p3=1,p5=1;
        for (int i=2;i<n+1;i++){
            int num2=dp[p2]*2,num3=dp[p3]*3,num5=dp[p5]*5;
            dp[i]= Math.min(Math.min(num2,num3),num5);
            if (dp[i]==num2) p2++;
            if (dp[i]==num3) p3++;
            if (dp[i]==num5) p5++;
        }
        return dp[n];
    }
}

class Offer60{
    public double[] dicesProbability(int n) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6.0);
        for (int i = 2; i <= n; i++) {
            double[] tmp = new double[5 * i + 1];
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j + k] += dp[j] / 6.0;
                }
            }
            dp = tmp;
        }
        return dp;
    }
}